// 给定一个二叉树，返回它的 后序 遍历。

// 示例:

// 输入: [1,null,2,3]  
//    1
//     \
//      2
//     /
//    3 

// 输出: [3,2,1]
// 进阶: 递归算法很简单，你可以通过迭代算法完成吗？

#include "stdc++.h"

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

/* 递归
*/
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        vector<int> res{};
        postOrder(root, res);
        return res;
    }
    void postOrder(TreeNode* root, vector<int>& res) {
        if (root == nullptr) {
            return;
        }
        if (root->left != nullptr) {
            postOrder(root->left, res);
        }
        if (root->right != nullptr) {
            postOrder(root->right, res);
        }
        res.emplace_back(root->val);
    }
};

/* 迭代
*/
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        vector<int> res{};
        stack<TreeNode*> stk{};
        TreeNode* pre{nullptr};
        while (root != nullptr || !stk.empty()) {
            // 有左加左
            while (root != nullptr) {
                stk.emplace(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            if (root->right  == nullptr || root->right == pre) {
                res.emplace_back(root->val);
                pre = root;
                root = nullptr;
            } else {
                // 右子树不为空
                stk.emplace(root);
                root = root->right;
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        vector<int> res{};
        stack<TreeNode*> stk{};
        stk.push(root);
        while (!stk.empty()) {
            TreeNode* node = stk.top();
            stk.pop();
            res.push_back(node->val);
            if (node->left) {
                stk.push(node->left);
            }
            if (node->right) {
                stk.push(node->right);
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

/* 前中后迭代统一写法
*/
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        vector<int> res{};
        stack<TreeNode*> stk{};
        stk.push(root);
        while (!stk.empty()) {
            TreeNode* node = stk.top();
            if (node != nullptr) {
                // stk.pop();
                // stk.push(node);         // 中
                stk.push(nullptr);         // 标记
                if (node->right) {
                    stk.push(node->right); // 右
                }
                if (node->left) {
                    stk.push(node->left);  // 左
                }
            } else {
                stk.pop();
                node = stk.top();
                stk.pop();
                res.push_back(node->val);
            }
        }
        return res;
    }
};